由于字数太多，导致在这里打字会很卡，会新开一个帖子。
观前须知：
1.由于 作者的精神状态十分低下。所以可能会出现讲题讲到一半开始胡言乱语的情况。不用太过在意。
2.每一句话的基础是作者浅薄的知识储备。如果你认为我讲的不对，欢迎指正。但是请友好用语。因为作者心理素质奇差无比。
————————————————————————————————————————
算法是一张网。
我学习过的：
背包DP 区间DP 树形DP 状压DP 线性DP
BFS DFS 剪枝 记忆化搜索
最短路 最小生成树 差分约束 连通块 多层图（？）
并查集 堆 树状数组
单调队列 前缀和 栈 队列 ST表 差分 单调栈
最大公约数gcd 扩展欧几里得
模拟 贪心 递推 倍增 二分 递归 枚举 分治 排序 STL
树的遍历 lca
然后要把它们之间的逻辑一一梳理开，合并在一起。
由于 我在备考GESP八级。所以 会优先考虑 目前在弄的算法。
所以先从最短路开始。
我会做难度从黄到蓝的最短路，并且逐一进行认真的分析。
这里可能会放一些一个算法单独出现的题目。首先是为了难度铺垫。其次是，用这些题目加深对这个算法的理解，从而更好地与其他算法相结合。
一.最短路
最短路有很多种。可以从很多个方面来区分。
比如说分成单源最短路，多源最短路。
比如说分成dijkstra，SPFA，FLOYD。
接下来，我们一题一题分析它的易错点和用处。
先从用的最多的dijkstra入手。
一切的一切先从模板开始吧。
单源最短路模板（dij)
好想学花滑啊喵。小祈真可爱。
但是不太行。
总觉得计算机是有些枯燥和无聊的。但是既然选择了这条路，就坚定不移的走下去。
每通过一题，就想象自己实在聚光灯下谢幕了一次。
”正因为如此，我才站在这里。“
这个是模板代码，我在字里行间做了批注易错点。
前面忘记分析算法的时间复杂度了。现在闪现一下。
这个其实是dijkstra的优化版本。
dijkstra使用贪心策略，每次选取距离起点最近的为便利顶点作为松弛顶点。（from yuilice)
普通的dij是直接枚举。时间复杂度为O(n^2)。
优化的dij使用优先队列进行筛选，时间复杂度为O(nlogn)。
赚钱
我看着 天上的星 晦暗 晦暗如你。
”若以物喻己，恰似秋之萤。“
若以物喻你，恰似南山雪。
这道题不算难。大致思路是，将直接同行路径视作花费为零的路径。然后每个点的价值是d。求取最大价值。
等一下。这道题好像要用SPFA。
那我们顺带着把SPFA模板放一下好了。
SPFA模板
啊。”若以物喻己，恰似秋之萤。“
老师说我的小说总是青春伤痛文学。从六年级到八年级都没变过。
但是我就喜欢这种感觉。本该是热烈的年龄有着不应该背负的痛苦。
不是成年人血淋淋的痛。但是是清淡的飘渺的如影随形的。
像是下了一场小雨一样。开始下了就没停过。
我累累累累累累累。但是这是我自己选的路。打碎了牙和着血吞进肚子里都得走下去。
我操了。我编译器炸了。花了半小时去调编译器。
这就是一道比较普通的SPFA模板题目。
比较特殊的是，它初始最大值要求要赋值为1e9。不然会错。
（其实这个例题我找的不是特别好。应该用判断负环的那种试试看。）
好的，岔子结束，我们继续赚钱。
“被神明青睐的人。”
先放代码。
这边大致的思路前面其实已经做过的分析了。
要用SPFA的原因是可能有“负环”。
我做了一点手脚。
将求最短路变成了求“最长路”。
所以负环打了双引号。
这边的负环指的是它可能会越来越大。
分析：
这道题目是纯SPFA，没有混合任何其他的算法。
那么，能分析的点就在于其思路。
这题主要的思路是两层：
1.将P条单向路径算成是花费为零的路。
2.用“最短路”的壳，求取最大值。
这给我们启示：
“最短路”并不只能是求取图上问题的算法。也不是只能够求取最短路的算法。
它是求“最值”的算法。
时间复杂度分析（不保证一定分析的是对的。因为我很不擅长分析这个）：
（前面已经分析过了DIJ现在直接分析SPFA）：
对于每一个点，最坏的情况它可能会被放入队列m次（边的数量）（因为SPFA是争对有负环的题目，所以这种情况是很有可能发生的哦）
那么（最坏）时间复杂度是O(nm)。如果n>=1e6且m>=1e5。
那么你就会超时。
所以用SPFA需要谨慎行事。
然后我们接着看下一题。
（我大概会做五六道黄题，然后步入绿）
请柬
“飞鹰”。人生在世，不过**二字。哈哈哈哈哈哈。
额。这道题的题目其实有点容易误解。
不过可以看样例。
这道题说人话就是：求出点1到所有点的距离。求出所有点到点1的距离。将它们加起来。
唯一的问题是。它是单向边。而。如果。
要跑一遍所有顶点的最短路。毫无疑问。会超时。
那么此时，我们找出题目的弱点：它只要所有点到点1的距离。
而不对其他店的距离做要求。
我们得出结论：反向建边。然后再从点一跑最短路。
好的差不多了。
上代码：
嗯。大概就是这样。
不过我卡了很久的一点是：开longlong。
开longlong是很容易开不全的。所有的一切与边权相关的东西，都是要开long long的。
所以要开longlong的题目最好是先静态检查三遍。
分析：
这道题也依然是DIJ独奏。
那么也还是单独分析思路的环节。
这边思路最显著的点就是：反向建边。
但如过只是局限于将它作为技巧，它的应用场合，可能并不是非常广泛。
所以，我们要尝试将技巧转化为思想。
这个思想就是：
当题目需要重复使用n遍相同技巧，而最后要求的结果又并不是苛刻的，反而是集中于一点的或者可以突破的；那我们要尝试一些做法，使其得以一次运行出想要的结果。
往往这个方法就是从另一个角度去想，去建边，去构图。
最短路补充：
OK。开下一题。
新年好
额。注意到一共只有五个目的地。
所以。我们可以考虑，将五个目的地的最短路全部预处理出来。
然后。进行1-5全排列DFS。
差不多。
上代码。
本题的难点是：代码有点难调。
其他的没了。
分析：
依旧是最短路单打独斗。
欸不对。
本题是DFS（全排列）+最短路的做法。
不过DFS是基础DFS，如果要在DFS上再做手脚，这题就是绿色了。
第一眼看到本题，会犹豫一下要怎么求取节点一到其他五个点串在一起的最短距离。
先想到最短路：图上边权最值问题，我们先考虑最短路。（确实是最普遍的（至少是我所明确的））
然后，怎么明智的使用最短路。
由于，只有五个节点。聪慧的你，肯定会第一时间想到，以五个顶点为起点，利落地都跑一遍最短路。
毕竟，不会超时。
然后，怎么去求取这五个顶点之间的最短距离呢。
现在，再想最短路如何去做，显然是不明智的选择。
只有五个顶点。全部都需要碰到。
wow。DFS全排列！
（这是因为，能够承担的其这个复杂度。）
你需要明白，题目给出数据，不是白给。
需要学会像上一题那样，分析题目的弱点。
再结合其弱点，匹配相应的武器（即算法）。
<=10 。太特殊了。
只要你有足够的DFS练习量。
几乎是一眼就能想到。
此时此刻，我们的网终于有了第一条丝线。
下一题！
糖果共享
这道题目拿到手之后就会发现小朋友们呈环状。
不过对于最短路来说，这只是边加在哪里的问题。
但是对于其他的算法。那就是需不需要断环成链的问题。
本题不难。好像就是需要加边的时候懂点手脚即可。
哈哈哈哈哈哈。“新的一天，要做被神明青睐的人。”
这其实是一个梗。来源于我们班老师说“我们班现在已经有同学被四校（上海最好的四所高中）青睐了。”而后附加了一系列的赞美。说的好像马上就要上天堂了一样。
过了。
喜欢高速打字。像是在飙车一样。
展示代码：
这道题普遍做法似乎使用的是DP。
那等我说一下我最短路的做法，然后就看一下DP怎么写。
关于我怎么用最短路做的：
将老师设为起点，将所有人的传递时间视作边即可。
再跑一次最短路就过了。
分析：
这道题，并没有图的壳子。
而是一个隐藏款。那么在考场中，如何准确地识别出，这是一道最短路的题目呢？
首先看到题目的要求：最快什么时候拿到糖果。
我们一般考虑使用：DP，贪心，最短路。（以我目前的知识储备进行判定。）
看到n<=2e5。这把一般最短路。（或者反悔贪心（单凭上述两个信息进行判断，而不是根据题目全局。））
而且是Dijkstra。因为DP一般是O(n^2)时间复杂度的（据我目前所知）（虽然这题确实是O（n)时间复杂度，但是线性DP比较稀有）。
贪心，一般是O(n)的吧。它能开大数据为什么不开。
这就是 算法选择。
然后就是加边。如果我没记错的话，这个知识点应该是超级源点（应该是的）。
就是将所有点，都与点0建交。然后跑最短路。
那么。
哦。突然想起：记得开long long。
好的，接下来瓦达西去了解一下怎么用DP做。
哦。失策了。这么简单。
不应该去看题解的。应该自己想的[悲伤蛙.jpg]。
哦。也没想象中的这么简单。
先放代码喵：
思路：
阅读题目可知，一个小朋友一共有两次拿到糖果的机会。
